/*
 * Author:  Vector
 * Email:   mcvector.gu@gmail.com
 * Website: vivalavector.net
 * Description:
 *      Home work of introduction to algorithm
 *      This is a file to sort an int array with 7 sorting methods
 *      1.  Insertion sort
 *      2.  Selection sort
 *      3.  Bubble sort
 *      4.  Quick sort
 *      5.  Heap sort
 *      6.  Merge sort
 *      7.  Shell sort
 */
#include <iostream>
using namespace std;

//Insertion sort
//Average O(n^2), Best O(n), Worst O(n^2), stable 
void swap(int &a, int &b)
{
    int temp = 0;
    temp = a;
    a = b;
    b = temp;
}

void insertionSort(int *array, int len)
{
    int key;
    int arrayIndex;
    for(int i = 1; i < len; i++)
    {
        key = array[i];
        arrayIndex = i-1;
        while (arrayIndex >= 0)
        {
            if(key < array[arrayIndex])
            {
                array[arrayIndex+1] = array[arrayIndex];
            }
            else
            {
                break;
            }
            arrayIndex--;
        }
        array[arrayIndex+1] = key;
    }
}

//Insertion sort with gap
void insertionSortwithGap(int *array, int len, int increment)
{
    for (int i = increment; i < len; i++)
        for (int j=i; j >= increment && array[j] < array[j-increment]; j -= increment)
            swap(array[j], array[j-increment]);
}

//Shell sort
//Average: O(n log^2 n), Best O(n)
void shellSort(int *array, int len)
{
//Sort the sort with insertion sorting by step of 5, 3, 1 successively
    for ( int i = len/5; i > 5; i /= 5)         //gap = 5
        for (int j = 0; j < i; j++)
            insertionSortwithGap(array + j, len - j, i);

    for(int i = 0; i < len; i++)
    {
        cout<<array[i]<<"\t";
    }
    cout<<endl;
    
    for ( int i = len/3; i >3; i /= 3)
        for (int j = 0; j < i; j++)
            insertionSortwithGap(array+j, len - j, i);

    for(int i = 0; i < len; i++)
    {
        cout<<array[i]<<"\t";
    }
    cout<<endl;

    insertionSort(array, len);
                
}


//Selection sort
//Average O(n^2), Best O(n^2), Worst O(n^2), unstable
void selectionSort(int *array, int len)
{
    for (int i=0; i < len; i++)
    {
        int min = i;
        for (int j = i+1; j < len; j++)
            if (array[min] > array[j])
                min = j;
        //Swap ith elment and minth element
        swap(array[min], array[i]);
    }
}
//Bubble Sort
//Average O(n^2), Best O(n), Worst O(n^2), stable
void bubbleSort(int *array, int len)
{
    for (int i=len-1; i > 0; i--)
        for (int j=0; j < i; j++)
            if (array[j] > array[j+1])
                //swap array[j] and array[i]
                swap(array[j], array[j+1]);
}

//merge sort
void merge(int *arrayToMerge, int p, int q, int r)
{
    //this function is to merge two sorted part of array arrayToMerge into
    //a bigger sorted array. It's a part of merge sort.
    int index1 = 0;
    int len1 = q-p+1;
    int index2 = 0;
    int len2 = r-q;
    int mainIndex = p; 
    //create to array to store two sorted sub array
    int *array1 = new int[len1];
    int *array2 = new int[len2];
    for(int i = 0; i < len1; i++)
        array1[i] = arrayToMerge[p+i];
    for(int i = 0; i < len2; i++)
        array2[i] = arrayToMerge[q+1+i];

    //merge two arrays and copy to origin array

    while(mainIndex <= r)
    {
        //if reach the end of the sub arraise
        if(index1 >= len1)
            //copy all rest of the elements from array2 to the main array
            arrayToMerge[mainIndex++] = array2[index2++];

        else if(index2 >= len2)
            //copy all rest of the elements from array1 to the main array
            arrayToMerge[mainIndex++] = array1[index1++];

        //no end of any array have been reached
        else
            if(array1[index1] > array2[index2])
                arrayToMerge[mainIndex++] = array2[index2++];
            else
                arrayToMerge[mainIndex++] = array1[index1++];
    }
}


void mergeSort(int *array, int start, int end)
{
    if (end > start)
    {
        int mid = (start + end)/2;
        mergeSort(array, start, mid);
        mergeSort(array, mid+1, end);
        merge(array, start, mid, end);
    }
}

//heap sort
void maxHeapify(int *rawArray, int root, int heapSize)
{
    //this function is used to make a tree of root to be a max heapfied heap;
    //this function gonna be called by heapSort
    int largest;
    int lChild, rChild;
    //Since the array is begin with 0, so there gonna be an lil bit different 
    lChild = (root<<1)+1;
    rChild = (root<<1)+2;
    if ( lChild < heapSize && rawArray[lChild] > rawArray[root])
        largest = lChild;
    else
        largest = root;
   
    if ( rChild < heapSize && rawArray[rChild] > rawArray[largest])
        largest = rChild;

    if (largest != root)
    {
        int temp = rawArray[largest];
        rawArray[largest] = rawArray[root];
        rawArray[root] = temp;
        maxHeapify(rawArray, largest, heapSize);
    }
}

void buildMaxHeap(int *rawArray, int heapSize)
{
    for( int i = (heapSize-1)/2 ; i >=0 ; i--)
        maxHeapify(rawArray, i, heapSize);
}
        
void heapSort(int *array, int len)
{
    int temp;
    int heapLen = len;
    buildMaxHeap(array, heapLen);
    for(int i = len - 1; i > 0; i--)
    {
        temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        heapLen--;
        maxHeapify(array, 0, heapLen);
    }
}


    
int partiton(int *arrayToPartition, int start, int end)
{
    //This function is used to seperate an array into two parts, all of the
    //elements in the left part are bigger than those in the right part, split
    //is based on the key, which is the last of the array
    int temp;
    int key = arrayToPartition[end];
    int i = start - 1;
    for(int j = start; j < end; j++)
    {
        if(arrayToPartition[j] < key)
        {
            i++;
            temp = arrayToPartition[j];
            arrayToPartition[j] = arrayToPartition[i];
            arrayToPartition[i] = temp;
        }
    }
    temp = arrayToPartition[i+1];
    arrayToPartition[i+1] = arrayToPartition[end];
    arrayToPartition[end] = temp;
    return i+1;
}


void quickSort(int *array, int start, int end)
{
    if (start < end)
    {
       int mid = partiton(array, start, end);
       quickSort(array, start, mid-1);
       quickSort(array, mid+1, end);
    }
}



int main()
{
    int source[] = {1, 3, 12, 5, 4, 10, 55, 32};
    cout<<"Processin' insertion sort...\n";
    insertionSortwithGap(source, 8, 2);
    for(int i = 0; i < 8; i++)
    {
        cout<<source[i]<<"\t";
    }
    cout<<endl;
    int source1[] = {1, 3, 12, 5, 4, 10, 55, 32 };
    /*
    cout<<"Processin' merge sort...\n";
    mergeSort(source1, 0, 7);
    for(int i = 0; i < 8; i++)
    {
        cout<<source1[i]<<"\t";
    }
    cout<<endl;
    
    cout<<"Processing heap sort...\n";
    heapSort(source1, 8);
    
    for(int i = 0; i < 8; i++)
    {
        cout<<source1[i]<<"\t";
    }
    
    cout<<endl;

    cout<<"Processing quickSort sort...\n";
    quickSort(source1, 0, 7);
    for(int i = 0; i < 8; i++)
    {
        cout<<source1[i]<<"\t";
    }
    cout<<endl;

    cout<<"Processing selectionSort sort...\n";
    selectionSort(source1, 8);
    for(int i = 0; i < 8; i++)
    {
        cout<<source1[i]<<"\t";
    }
    cout<<endl;


    cout<<"Processing bubbleSort sort...\n";
    bubbleSort(source1, 8);
    for(int i = 0; i < 8; i++)
    {
        cout<<source1[i]<<"\t";
    }
    cout<<endl;
    */

    cout<<"Processing shellSort sort...\n";
    shellSort(source1, 8);
    for(int i = 0; i < 8; i++)
    {
        cout<<source1[i]<<"\t";
    }
    cout<<endl;


    return 0;
}
    


